package pers.qianyu.month_202012.date_20201225.dp_bag;

import org.junit.*;
import pers.qianyu.util.*;

/**
 * 799. 背包问题VIII
 * https://www.lintcode.com/problem/backpack-viii/description
 * - 使用的是完全背包的思想
 *
 * @author mizzle rain
 * @date 2020-12-25 16:56
 */
public class BackPackVIII {
    /**
     * @param n:      the value from 1 - n
     * @param value:  the value of coins
     * @param amount: the number of coins
     * @return: how many different value
     */
    public int backPackVIII(int n, int[] value, int[] amount) {
        int len = value.length;
        // dp[i] 表示能不能凑成 i
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        int res = 0;
        for (int i = 0; i < len; i++) {
            // cnt[j] 表示凑成 j 所使用的物品数目
            int[] cnt = new int[n + 1];
            for (int j = value[i]; j <= n; j++) {
                if (dp[j - value[i]] && !dp[j] && cnt[j - value[i]] < amount[i]) {
                    cnt[j] += cnt[j - value[i]] + 1;
                    res++;
                    dp[j] = true;
                }
            }
        }
        return res;
    }

    public int backPackVIII2(int n, int[] value, int[] amount) {
        int len = value.length;
        // dp[i] 表示能不能凑成 i
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 0; i < len; i++) {
            // cnt[j] 表示凑成 j 所使用的物品数目
            int[] cnt = new int[n + 1];
            int v = value[i];
            int a = amount[i];
            for (int j = v; j <= n; j++) {
                if (cnt[j - v] < a && dp[j - v] && !dp[j]) {
                    cnt[j] = cnt[j - v] + 1;
                    dp[j] = true;
                }
            }
            ArrayUtil.printArrayAsMarkdownTable(v, cnt);
        }
        int res = 0;
        for (boolean b : dp) if (b) res++;
        return res - 1;
    }

    // 超时
    public int backPackVIII3(int n, int[] value, int[] amount) {
        int len = value.length;
        // dp[i] 表示能不能凑成 i
        boolean[] dp = new boolean[n + 1];
        dp[0] = true;
        for (int i = 0; i < len; i++) {
            int v = value[i];
            int a = amount[i];
            for (int j = 0; j < a; j++) {
                for (int k = n; k >= v; k--) {
                    dp[k] = dp[k - v] | dp[k];
                }
            }
        }
        int res = 0;
        for (boolean b : dp) if (b) res++;
        return res - 1;
    }

    public static void main(String[] args) {
        int n = 5;
        int[] value = {1, 4};
        int[] amount = {2, 1};
        int result = new BackPackVIII().backPackVIII2(n, value, amount);
        Assert.assertEquals(result, 4);
    }
}
